#include "initAnts.h"

// returns the absolute value of a number; used in distance function

int abs(int x) {
    if (x >= 0)
        return x;
    return -x;
}

int sgn(int x) {
    if (x >= 0)
        return 1;
    else
        return -1;
}

// "-" znamena ze to je na S, "+" je na N
int row_distance(int row1, int row2, struct game_info *Info) {
    int dr;
    int abs1, abs2, r12;

    r12 = row1 - row2;
    abs1 = abs(r12);
    abs2 = Info->rows - abs(r12);

    if (abs1 > abs2)
        dr = -1 * sgn(r12) * abs2; // opacny smer nez r12
    else
        dr = r12;
    return dr;
}

// "-" znamena E, "+" znamena W
int col_distance(int col1, int col2, struct game_info *Info) {
    int dc;
    int abs1, abs2, c12;

    c12 = col1 - col2;
    abs1 = abs(c12);
    abs2 = Info->cols - abs(c12);

    if (abs1 > abs2)
        dc = -1 * sgn(c12) * abs2;
    else
        dc = c12;

    return dc;
}

// returns the distance between two items on the grid accounting for map wrapping

int distance(int row1, int col1, int row2, int col2, struct game_info *Info) {
    int dr, dc;
    int abs1, abs2;

    abs1 = abs(row1 - row2);
    abs2 = Info->rows - abs(row1 - row2);

    if (abs1 > abs2)
        dr = abs2;
    else
        dr = abs1;

    abs1 = abs(col1 - col2);
    abs2 = Info->cols - abs(col1 - col2);

    if (abs1 > abs2)
        dc = abs2;
    else
        dc = abs1;

    return sqrt(pow(dr, 2) + pow(dc, 2));
}

// returns the steps to reach two items

int steps_distance(int row1, int col1, int row2, int col2, struct game_info *Info) {
    int dr, dc;
    int abs1, abs2;

    abs1 = abs(row1 - row2);
    abs2 = Info->rows - abs(row1 - row2);

    if (abs1 > abs2)
        dr = abs2;
    else
        dr = abs1;

    abs1 = abs(col1 - col2);
    abs2 = Info->cols - abs(col1 - col2);

    if (abs1 > abs2)
        dc = abs2;
    else
        dc = abs1;

    return dr+dc;
}

// Zjistuji, zda je volne pole pro posun mravence
char can_ant_move(int ant_row, int ant_col, char plan_char_move, struct game_info *Info){
    #define UP -Info->cols
    #define DOWN Info->cols
    #define LEFT -1
    #define RIGHT 1
    int offset = ant_row*Info->cols + ant_col;
    char obj;
    switch (plan_char_move){
        case 'W' :
            if (ant_col != 0)
                obj = Info->map[offset + LEFT];
            else
                obj = Info->map[offset + Info->cols - 1];
            break;
        case 'E':
            if (ant_col != Info->cols - 1)
                obj = Info->map[offset + RIGHT];
            else
                obj = Info->map[offset - Info->cols + 1];
            break;
        case 'N':
            if (ant_row != 0)
                obj = Info->map[offset + UP];
            else
                obj = Info->map[offset + (Info->rows - 1)*Info->cols];
            break;
        case 'S':
            if (ant_row != Info->rows - 1)
                obj = Info->map[offset + DOWN];
            else
                obj = Info->map[offset - (Info->rows - 1)*Info->cols];
            break;
        default:
            obj='%';
            break;
    }
    if (obj == '.')
        return 1;
    else
        return 0;
}

// sends a move to the tournament engine and keeps track of ants new location

void move(int index, char dir, struct game_state* Game, struct game_info* Info) {
    fprintf(stdout, "O %i %i %c\n", Game->my_ants[index].row, Game->my_ants[index].col, dir);
    Info->map[Game->my_ants[index].row * Info->cols + Game->my_ants[index].col]='.';

    switch (dir) {
        case 'N':
            if (Game->my_ants[index].row != 0)
                Game->my_ants[index].row -= 1;
            else
                Game->my_ants[index].row = Info->rows - 1;
            break;
        case 'E':
            if (Game->my_ants[index].col != Info->cols - 1)
                Game->my_ants[index].col += 1;
            else
                Game->my_ants[index].col = 0;
            break;
        case 'S':
            if (Game->my_ants[index].row != Info->rows - 1)
                Game->my_ants[index].row += 1;
            else
                Game->my_ants[index].row = 0;
            break;
        case 'W':
            if (Game->my_ants[index].col != 0)
                Game->my_ants[index].col -= 1;
            else
                Game->my_ants[index].col = Info->cols - 1;
            break;
    }
    Info->map[Game->my_ants[index].row * Info->cols + Game->my_ants[index].col]='a';
    Game->my_ants[index].last_move=dir;
}

// opacny smer
char opposite_direction(char direction){
    switch (direction) {
        case 'N':
            return 'S';
        case 'S':
            return 'N';
        case 'W':
            return 'E';
        case 'E':
            return 'W';
        default:
            return -1;
    }
}

// direction to target
int get_d2t(int start_row, int start_col, int target_row, int target_col, struct game_info *Info){
    int ret_value=5;
    int dr = row_distance(start_row, target_row, Info);
    int dc = row_distance(start_col, target_col, Info);
    if (! ( (dr == 0) && (dc == 0)))
        if (dr == 0)
            if (dc > 0)
                ret_value = 4;
            else
                ret_value = 6;
        else if (dc == 0)
            if (dr > 0)
                ret_value = 8;
            else
                ret_value = 2;
        else if ((dr > 0) && (dc > 0))
            if (dr/2 >= dc)
                ret_value = 8;
            else if (dc/2 >= dr)
                ret_value = 4;
            else
                ret_value = 7;
        else if ((dr > 0) && (dc < 0))
            if (dr/2 >= -dc)
                ret_value = 8;
            else if (-dc/2 >= dr)
                ret_value = 6;
            else
                ret_value = 9;
        else if ((dr < 0) && (dc < 0))
            if (-dr/2 >= -dc)
                ret_value = 2;
            else if (-dc/2 >= -dr)
                ret_value = 6;
            else
                ret_value = 3;
        else if ((dr < 0) && (dc > 0))
            if (-dr/2 >= dc)
                ret_value = 2;
            else if (dc/2 >= -dr)
                ret_value = 4;
            else
                ret_value = 1;

    return ret_value;
}


void deinit_xmove(struct xmove *Xmove){
    if (Xmove->next !=0) {
        deinit_xmove(Xmove->next);
    }
    free(Xmove);
}

void gdeinit_xmove(struct xmove *Xmove){
    struct xmove *endXmove;
    while (Xmove != 0) {
        endXmove = Xmove->gnext;
        free(Xmove);
        Xmove = endXmove;
    }
}

// projdu list, jestli tam neni dany prvek
int is_xmove_pointer_in_list(struct xmove *newXmove, struct xmove *listXmove){
    if (listXmove == 0)
        return 0;
    if (listXmove == newXmove)
        return 1;
    return is_xmove_pointer_in_list(newXmove, listXmove->next);
}

// stejne porovnani, ale tentokrat pouze podle polohy, nikoli podle pointru
int is_xmove_in_list(int row, int col, struct xmove *listXmove){
    if (listXmove == 0)
        return 0;
    if ((listXmove->row == row) && (listXmove->col == col))
        return 1;
    return is_xmove_in_list(row, col, listXmove->next);
}

// pokud neni newXmove v list, tak ho tam pridam
struct xmove * insert_xmove(struct xmove *newXmove, struct xmove *listXmove){
    if (newXmove == 0)
        return listXmove;
    struct xmove *testXmove = 0;
    struct xmove *nextXmove = 0;
//    if (! is_xmove_in_list(newXmove->row, newXmove->col, listXmove) ) {
    {
        if (listXmove == 0)
            listXmove = newXmove;
        else if (newXmove->step + newXmove->dist <= listXmove->step + listXmove->dist){
            // zaradim jako prvni
            newXmove->next = listXmove;
            listXmove = newXmove;
        } else if (listXmove->next == 0){
            // zaradim jako druhy
            listXmove->next = newXmove;
        } else {
            // musim najit kam ho zaradit
            testXmove = listXmove;
            nextXmove = listXmove->next;
            while ( nextXmove !=0 ){
                if ((newXmove->step + newXmove->dist) <= (nextXmove->step + nextXmove->dist)){
                    // to znamena, ze jej zaradim pred nej
                    testXmove->next = newXmove;
                    newXmove->next = nextXmove;
                    break;
                } else {
                    testXmove = nextXmove;
                    nextXmove = testXmove->next;
                }
            }
            if (nextXmove == 0) { // tzn, ze jsem ho nezaradil, musim ho dat nakonec 
                newXmove->next = 0;
                testXmove->next = newXmove;
            }

        }
    }
    return listXmove;
}

// pokud neni newXmove v list, tak ho tam pridam
struct xmove * insert_xmove_at_first(struct xmove *newXmove, struct xmove *listXmove){
    if (newXmove != 0){
    newXmove->next = listXmove;
    listXmove = newXmove;
    }
    return listXmove;
}


// navrati hloubku tahu, pro ziskani daneho uzlu
int depth_xmove_prev(struct xmove *Xmove){
    if (Xmove == 0)
        return 0;
    return depth_xmove_prev(Xmove->prev) + 1;
}


// implementovana aStar na hledani cesty
char* plan_movement_aStar(int start_row, int start_col, int target_row, int target_col, struct game_info *Info){
    int length = 2; // aspon jedno pismeno a '\0'
    char last_move = ' ';
    char *roll_back_way;
    int new_row = 0, new_col = 0;
    struct xmove *Xmove;
    struct xmove *newXmove = 0;
    struct xmove *openXmove = 0;
    struct xmove *closeXmove = 0;
    struct xmove *endXmove = 0;
    // inicializuji zacatek
    Xmove = malloc(sizeof(struct xmove));
    endXmove = Xmove;
    Xmove->row = start_row;
    Xmove->col = start_col;
    Xmove->next = 0;
    Xmove->gnext = 0;
    Xmove->prev = 0;
    Xmove->dir = ' ';
    Xmove->step = 0;
    Xmove->dist = steps_distance(start_row, start_col, target_row, target_col, Info);
    //openXmove = Xmove;
    // expand :
    while ((Xmove != 0) && (Xmove->step < MOV_LEN - 1) && (length < 2*MOV_LEN))
                { //((openXmove != 0) || (( Xmove->row == target_row) && (Xmove->col == target_col)))
        // mam Xmove a zkusim ji expandovat
        //
        // nejprve W = -Info->cols
        new_row = Xmove->row;
        new_col = (Info->cols + Xmove->col - 1) % Info->cols;
        last_move = 'W';
        if ((new_row == target_row) && (new_col == target_col)) 
            break;
        if ((( Info->map[ Info->cols*new_row + new_col ] == '.' ) ||
            ( Info->map[ Info->cols*new_row + new_col ] == '*' )) &&
                (! is_xmove_in_list(new_row, new_col, closeXmove)) && 
                (! is_xmove_in_list(new_row, new_col, openXmove))) {
            // vytvorim newXmove 
            newXmove = malloc(sizeof(struct xmove));
            newXmove->gnext = endXmove;
            endXmove = newXmove;
            newXmove->row=new_row;
            newXmove->col=new_col;
            newXmove->prev = Xmove;
            newXmove->next = 0;
            newXmove->dir = last_move;
            newXmove->step = Xmove->step + 1;
            newXmove->dist = steps_distance(new_row, new_col, target_row, target_col, Info);
            // a ulozim do open
            openXmove = insert_xmove(newXmove, openXmove);
        }

        // nyni zkusim E
        new_row = Xmove->row;
        new_col = (Info->cols + Xmove->col + 1) % Info->cols;
        last_move = 'E';
        if ((new_row == target_row) && (new_col == target_col)) 
            break;
        if ((( Info->map[ Info->cols*new_row + new_col ] == '.' ) ||
            ( Info->map[ Info->cols*new_row + new_col ] == '*' )) &&
                (! is_xmove_in_list(new_row, new_col, closeXmove)) && 
                (! is_xmove_in_list(new_row, new_col, openXmove))) {
            // vytvorim newXmove 
            newXmove = malloc(sizeof(struct xmove));
            newXmove->gnext = endXmove;
            endXmove = newXmove;
            newXmove->row=new_row;
            newXmove->col=new_col;
            newXmove->prev = Xmove;
            newXmove->next = 0;
            newXmove->dir = last_move;
            newXmove->step = Xmove->step + 1;
            newXmove->dist = steps_distance(new_row, new_col, target_row, target_col, Info);
            // a ulozim do open
            openXmove = insert_xmove(newXmove, openXmove);
        }

        // nyni zkusim N
        new_row = (Info->rows + Xmove->row - 1) % Info->rows;
        new_col = Xmove->col;
        last_move = 'N';
        if ((new_row == target_row) && (new_col == target_col)) 
            break;
        if ((( Info->map[ Info->cols*new_row + new_col ] == '.' ) ||
            ( Info->map[ Info->cols*new_row + new_col ] == '*' )) &&
                (! is_xmove_in_list(new_row, new_col, closeXmove)) && 
                (! is_xmove_in_list(new_row, new_col, openXmove))) {
            // vytvorim newXmove 
            newXmove = malloc(sizeof(struct xmove));
            newXmove->gnext = endXmove;
            endXmove = newXmove;
            newXmove->row=new_row;
            newXmove->col=new_col;
            newXmove->prev = Xmove;
            newXmove->next = 0;
            newXmove->dir = last_move;
            newXmove->step = Xmove->step + 1;
            newXmove->dist = steps_distance(new_row, new_col, target_row, target_col, Info);
            // a ulozim do open
            openXmove = insert_xmove(newXmove, openXmove);
        }

        // nyni zkusim S
        new_row = (Info->rows + Xmove->row + 1) % Info->rows;
        new_col = Xmove->col;
        last_move = 'S';
        if ((new_row == target_row) && (new_col == target_col)) 
            break;
        if ((( Info->map[ Info->cols*new_row + new_col ] == '.' ) ||
            ( Info->map[ Info->cols*new_row + new_col ] == '*' )) &&
                (! is_xmove_in_list(new_row, new_col, closeXmove)) && 
                (! is_xmove_in_list(new_row, new_col, openXmove))) {
            // vytvorim newXmove 
            newXmove = malloc(sizeof(struct xmove));
            newXmove->gnext = endXmove;
            endXmove = newXmove;
            newXmove->row=new_row;
            newXmove->col=new_col;
            newXmove->prev = Xmove;
            newXmove->next = 0;
            newXmove->dir = last_move;
            newXmove->step = Xmove->step + 1;
            newXmove->dist = steps_distance(new_row, new_col, target_row, target_col, Info);
            // a ulozim do open
            openXmove = insert_xmove(newXmove, openXmove);
        }

        closeXmove = insert_xmove_at_first(Xmove,closeXmove);
        length++;

        Xmove = openXmove;
        if (Xmove != 0){
            openXmove = Xmove->next;
            Xmove->next = 0; // umazu nasledovniky z open
        }
        last_move='\0';
    }

    //insert_xmove(Xmove,closeXmove); // tohle uz nemusim, protoze je mazu po generovani.

    if (Xmove != 0){
        // tzn. byla nalezena cesta
        int depth = depth_xmove_prev(Xmove) + 1;
        roll_back_way = malloc(depth*sizeof(char));
        if (roll_back_way == 0){
            fprintf(stderr,"!!! MALLOC neinicializoval roll_back_way\n");
            return 0;
        }
        memset(roll_back_way, ' ', depth*sizeof(char));
        depth--;
        roll_back_way[depth] = '\0';
        depth--;
        roll_back_way[depth] = last_move;
        while((Xmove != 0) && (--depth >= 0)){
            roll_back_way[depth] = Xmove->dir;
            Xmove = Xmove->prev;
        }
    }

    // deinicializace
    //if (openXmove != 0)
    //    deinit_xmove(openXmove);
    //if (closeXmove != 0)
    //    deinit_xmove(closeXmove);
    gdeinit_xmove(endXmove);

    if (roll_back_way == 0){
        roll_back_way = malloc(sizeof(char));
        strcpy(roll_back_way,"\0");
    }
    return roll_back_way;
}


// just a function that returns the string on a given line for i/o
// you don't need to worry about this

char *get_line(char *text) {
    char *tmp_ptr = text;
    int len = 0;

    while (*tmp_ptr != '\n') {
        ++tmp_ptr;
        ++len;
    }

    char *return_str = malloc(len + 1);
    memset(return_str, 0, len + 1);

    int i = 0;
    for (; i < len; ++i) {
        return_str[i] = text[i];
    }

    return return_str;
}

// main, communicates with tournament engine

int main(int argc, char *argv[]) {
    char action = -1;
    char last_turn = 0;

    struct game_info Info;
    struct game_state Game;
    Info.map = 0;

    Game.my_ants = 0;
    Game.enemy_ants = 0;
    Game.food = 0;
    Game.dead_ants = 0;
    Game.hill = 0;

    while (42) {
        int initial_buffer = 100000;

        char *data = malloc(initial_buffer);
        memset(data, 0, initial_buffer);

        *data = '\n';

        char *ins_data = data + 1;

        int i = 0;

        while (1 > 0) {
            ++i;

            if (i >= initial_buffer) {
                initial_buffer *= 2;
                data = realloc(data, initial_buffer);
                ins_data = data + i;
                memset(ins_data, 0, initial_buffer - i);
            }

            // ctu znaky az do konce radku...
            *ins_data = getchar();

            if (*ins_data == '\n') {
                // konec radku... zpracuji co jsem dostal...
                char *backup = ins_data;

                // previnu se na zacatek toho co jsem cetl...
                while (*(backup - 1) != '\n') {
                    --backup;
                }
                // ziskam pointer na radku...
                char *test_cmd = get_line(backup);
                // pokud je to nejaky prikaz zastavim cteni
                //  a zpracuji, co jsem dostal...
                if (strcmp(test_cmd, "go") == 0) {
                    action = 0; 
                    free(test_cmd);
                    break;
                }
                else if (strcmp(test_cmd, "ready") == 0) {
                    action = 1;
                    free(test_cmd);
                    break;
                }
                else if (strcmp(test_cmd, "end") == 0) {
                    action = 2;
                    free(test_cmd);
                    break;
                }
                free(test_cmd);
            }

            ++ins_data;
        }

        if (action == 0) {  // go ... 
            // dostal jsem info o kolo a muzu se snazit...
            if (! last_turn ) {
                char *value = data;
                while (*++value != ' ');
                ++value;

                Info.current_turn = atoi(value);

                while (*++value != '\n');
                ++value;

                _init_map(value, &Info);
                _init_game(&Info, &Game);
                do_turn(&Game, &Info);
                free(data);
                fprintf(stdout, "go\n");
                fflush(stdout);
            } else { // posledni kolo...
                _deinit_map(&Info);
                free(data);
                fprintf(stdout, "go\n");
                fflush(stdout);
                break;
            }
        }
        else if (action == 1) {  // ready ...
            // dostal jsem info na zacatek,
            // predpripravim si struktury...
            _init_ants(data + 1, &Info);

            Game.my_ant_index = -1;

            free(data);
            fprintf(stdout, "go\n");
            fflush(stdout);
        }else if (action == 2){  // end ...
            // je posledni kolo
            last_turn = 1;
            free(data);
        } else
            free(data);

    }
}

// logovaci fce
void debug_log (char * text) {
    /*
    FILE * fout;
    fout = fopen("mAnts.log","a+");
    fprintf(fout,text);
    fclose(fout);
    */
    fprintf(stdout, "%s\n", text);
    fflush(stdout);
}
